package org.xiaojinlong.algo;

/**
 * Jin Long
 * 2015/8/27
 */
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;

    public MaxPQ() {

    }

    public MaxPQ(int capacity) {
        pq = (Key[]) new Object[capacity + 1];
    }

    // 在尾部添加节点，然后让它向上游
    public void insert(Key k) {
        pq[++N] = k;
        swim(N);
    }

    public Key delMax() {
        return null;
    }

    public boolean isEmpty() {
        return true;
    }

    public Key max() {
        return null;
    }

    public int size() {
        return 0;
    }

    // Promotion
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    private boolean less(int a, int b) {
        return (pq[a].compareTo(pq[b]) < 0);
    }

    private void exch(int a, int b) {
        Key swap = pq[a];
        pq[a] = pq[b];
        pq[b] = swap;
    }

    public static void main(String[] args) {
        MaxPQ<Integer> maxPQ = new MaxPQ<>(3);
        System.out.println("this can compile!!");
    }
}
